/**
 * User: 86156
 * Date: 2023-04-14
 * Time: 17:16
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {7, 13, 21, 30, 38, 44, 52, 53};

        int flag = BinarySearchBalance(arr,30);

        System.out.println(flag);

    }

    public static int BinarySearchBalance(int [] arr,int target){
        /*
        * 左闭右开的区间 left 可能是指向的元素 right不可能是指向的元素
        * 循环的平均次数减少了
        * */
        int left = 0;
        int right = arr.length;

        while (1<(right-left)) {
            int mid = (left+right)>>>1;

            if(target<arr[mid]){
                right = mid;
            }else{
                left = mid;
            }
        }

        if(arr[left] == target){
            return left;
        }else{
            return -1;
        }
    }

    public static int BinarySearchBasic(int[] arr,int target){
        int left = 0;
        int right = arr.length-1;

        // 元素在最左边 判断L次   元素在最右边  判断2L次  引出二分查找平衡版
        while(left<=right){
            int mid = (left+right)>>>1;
            if(target == arr[mid]){
                return mid;
            } else if (mid<target) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        return -1;
    }


    // j一定不是要查找的元素 效率更高
    public static int BinarySearchAlternation(int[] arr,int target){
        int left = 0;
        int right = arr.length;//第一处

        while(left<right){ // 第二处
            int mid = (left+right)>>>1;
            if(target == arr[mid]){
                return mid;
            } else if (mid<target) {
                left = mid; //第三处
            } else {
                right = mid-1;
            }
        }
        return -1;
    }
}

/*
* 问题  int mid = (left+right)/2 有没有问题
*
* 答: 有问题,如果right的值为 Integer.MAX_VALUE-1 ,那么第二次循环时将有可能越界
* 越界: left = (Integer.MAX_VALUE-1)/2 right = Integer.MAX_VALUE-1
*       mid = ????
*
* 改善方法: int mid = (left+right)>>>1;
* >>>: 无符号右移,最高位永远补零
* */
